The present invention relates to multiplex communication systems for transferring information in packets and more particularly, to processing of address header information to perform sequencing of header compressed packets to ensure proper output sequence order of packets in a multilayered network architecture.
Modern communications networks carry increasing amounts of packet traffic which is associated with real-time voice, video, and related data. The Internet, for example, is seeing many new applications which take advantage of what is a relatively less costly alternative to conventional telephone call connections for sending a variety of data including real time voice and video. Trends toward real time applications over the Internet are driven in part by increasingly powerful computers being installed in private homes and the proliferation of the Internet as a focal point for various on-line activities such as holding voice conversations, listening to music, watching video clips, and the like. Unlike Internet communications which occur between computers on high bandwidth commercial connections, bandwidth in a typical home is limited by connectivity constraints imposed by modem speed, line quality, and the like.
Further compounding the basic problem of limited bandwidth, is the limitation on the amount of actual information transmitted as a result of packet overhead due to protocol headers. Basic Internet protocols were developed primarily for making sure that packets were delivered accurately end to end at a time when little consideration was paid to real time issues.
Three layer interface architectures including protocols such as X.25, for example, were developed for controlling transfer at the lower levels while higher layer protocols were developed to control more sophisticated functions (see, “Open Systems Interconnect (OSI)—New International Standards Architectures and Protocols for Distributed Information Systems,” special issue, Proceedings of the IEEE, H. C. Folts and R. des Jardins, eds., vol. 71, no. 12, December 1983). According to the design philosophy, lower layer functions were contemplated to be “transparent” to higher layer functionality and thus much of what can be accomplished at the lower layers is limited only by the ability of lower layer hardware and software to preserve that transparency. At the lowest layer, the Physical Layer, a protocol specification governs the physical connection between devices, such as, for example, the X.21 protocol. Next, the Data Link Layer specifies the protocol for, for example, accepting packets from higher layers and placing them into, for example, HDLC frames for transfer across the Physical Layer. The Data Link layer further may accept framed information from the Physical Layer and unpack it for transfer up to the Network Layer. At the Network Layer, or packet layer, multiple logical connections may be established and addresses attached to packets based on several assumptions including that successful end to end delivery is not guaranteed, that orderly delivery is not guaranteed, and that packets or “datagrams” are delivered one at a time each containing information such as destination address, and the like.
It is important to note that while various lower layers are discussed herein, datagrams from higher layers may form the input to a Network Layer process or system, which in turn provide input to successively lower layers, and eventually to the destination. Higher layer datagrams input to a Network Layer entity may be input from, for example, a Transport Layer process or system. A typical and well know transport layer protocol is the Transport Control Protocol (TCP) although other Transport Layer protocols are known and used. In particular, the User Datagram Protocol (UDP) may often be used as a Transport Layer protocol. UDP is a protocol which defines a connectionless datagram service. A Transport Layer process or system implementing UDP may produce self-contained data packets which include destination routing information.
A ubiquitous protocol for Network Layer communications over the Internet is the Internet Protocol (IP). The IP specification includes an enumeration of fields associated with the IP header which fields contain information about an associated packet including information for determining how the packet should be delivered. The IP header fields will be described in greater detail herein below. For a more complete understanding of the contents of the IP header, see “Internet Protocol Specification”, E. J. Postel, SRI International, Menlo Park, Calif., September 1981, RFC791.
For Data Link Layer communications, Point-to-Point-Protocol (PPP) has become a dominant protocol. PPP includes three main components: a method of encapsulating multi-protocol datagrams, a datagram being a unit of transmission in the network layer (such as IP), a link control protocol (LCP) for establishing, configuring and testing the data-link connection, and a family of network control protocols (NCP) for establishing and configuring different network-layer protocols.
PPP is designed to transport packets between two so-called peers, i.e. the two ends of a link conforming to the protocol. Accordingly, the LCP may be used to agree upon the encapsulation format options, handle varying limits on sizes of packets, detect configuration errors, and terminate the link. Other optional facilities are the authentication of the identity of its peer on the link, and the determination when a link is functioning properly and when it is failing. PPP links-provide full-duplex simultaneous bidirectional operation. A definition of PPP may be found in the Networking Group Request for Comments RFC 1661, “The Point to Point Protocol” editor W. Simpson, July 1994.
Communication across a link established using PPP is accomplished such that a datagram associated with a protocol may be encapsulated into one or more frames. A frame, as described above, may include a header and/or a trailer, along with some number of units of data. However, it is conventional that an entire packet is mapped into a frame. Conventional framing breaks down however during conditions of heavy network congestion where fragmentation methods may be used to improve flow control management. Congestion giving rise to latency may be a particular problem for real time data such as voice or video, VoIP, Telnet, and the like. Such real time data formats have little or no tolerance to packet latency, jitter, packet reordering and related problems. Problems associated with the multilink environment only amplify the unique real time packet data requirements.
To ease congestion, one solution known as Link Fragmentation and Interleaving (LFI) is proposed in the White Paper entitled “Cisco™ Software Quality of Service Solutions”, Apr. 8, 1999, by Cisco Systems. In LFI, delay and jitter are reduced by breaking up large datagrams and interleaving time sensitive packets with the resulting packet fragments. LFI is contemplated for relatively low speed links where serialization delay is the predominant delay factor. LFI simply requires that PPP be configured to allow for interleaving. Otherwise, LFI is transparent to PPP.
Certain problems arise associated with conventional LFI and related data transfer which provide for PPP based scheduling and sequencing related primarily to delay waiting for, for example, long packets to be transferred. Such delay may create round trip delays associated with interactive real time data, such as a voice conversation, of close to a second. By, for example, fragmenting packets of various priorities larger than a predetermined size, high priority packets or fragments thereof may be sent between fragments of lower priority packets. Existing PPP specifications already provide for fragmentation by providing sequence numbers and begin and end bits in the PPP encapsulation format. However, existing PPP specifications do not provide for the suspension of transfer of fragments of one packet in order to send another, due to contiguous packet numbering schemes. Moreover, existing PPP specifications do not accomodate packet dropping which may occur at layers below PPP, for example, at the Physical Layer.
Regardless of the methods of scheduling fragments contemplated, problems arise in implementation. In particular, it should be noted that the lower three protocol layers and associated protocols including, for example, UDP, IP, and PPP, along with the physical layer typically reside on hardware resources, such as routers, which may introduce limitations that are detrimental to the benefits gained from fragmentation and other scheduling methods. In particular, a router, for example, may typically queue outbound packets together in the same transmit queue once priority or the like has been established. The configuration of a typical outbound packet queue is generally First In First Out (FIFO) and has a level of intrinsic delay associated with the queue depth. Further, a router experiencing high traffic levels and using a typical outbound packet queue raises the possibility of packet dropping when congestion occurs, even when using LFI, multi-link PPP or the like. If packets are forced to be dropped from downstream queues after IP or PPP scheduling occurs, problems related to packets received out of sequence may occur. Depending on the link configuration, request for retransmission of the missing packets, for example, may cause delay and degradation of real time data.
Packet dropping can be particularly troublesome when used in conjunction with other methods of reducing congestion such as, for example, header compression. By compressing or discarding certain portions of information contained in a typical header, header compression methods reduce the overall size of the datagram or packet. This is particularly important in the case of small packets typically used for real time data transfer applications where the header may represent close to 100% packet overhead. Although, header compression may be performed at various stages, problems arise due to an assumption which must be made in the art when using header compression that packet reordering or resequencing, including the effects of packet dropping, will not occur.
When a header-compressed (HC) packet is lost or discarded due to, for example, queue backup, the existence of a missing packet may typically be discovered at a decompressor. The decompressor located at a peer layer in a receiver node may signal back to a transmitter peer layer compressor to transmit, for example, a full header. Until a full header is received by the decompressor, all newly arrived packets will be discarded. Such an approach may function well as a protection against link errors, but such scenarios may be better managed by, for example, dealing with queue control at the transmitter and dealing with packet sequencing upstream at the scheduler if packets need to be dropped as further described in U. S. Pat. No. 6,577,596, supra. Thus, in accordance with one aspect of a HC based approach, a sequence number may be assigned during packet compression, i. e., in the PPP-layer, such that resulting packet dropping problems only affect operation at the PPP layer. Existing approaches however have drawbacks in that conventional approaches for dealing with packet dropping at the PPP layer add nearly as much header overhead as was saved originally with header compression techniques and do not address the problem of packet dropping at layers below PPP. For more general information on header compression see Internet Engineering Task Force (IETF), INTERNET DRAFT, “Providing Integrated Services Over Low-bitrate Links”, June 1999, expires: December 1999, by Carsten Borman, and see also Networking Group Request for Comments RFC 1144, “Compressing TCP/IP Headers for Low-Speed Serial Links”, editor V. Jacobson, February 1990.
Therefore, it would be appreciated in the art for a method and apparatus which reduces the adverse effects of packet dropping at the Physical Layer in header compression based packet communication systems.